package advance.day04;

import java.util.*;

/**
 * 描述：
 *      描述大楼的轮廓
 * @author hl
 * @version 1.0
 * @date 2020/11/9 15:19
 */
public class Building_Outline {
    public static class Node{
        int posi;
        int h;
        boolean isUp;

        public Node(int posi, int h, boolean isUp) {
            this.posi = posi;
            this.h = h;
            this.isUp = isUp;
        }
    }
    //自定义nodes的比较规则
    public static class MyComparator implements Comparator<Node>{
        @Override
        public int compare(Node o1, Node o2) {
            if (o1.posi != o2.posi) {
                return o1.posi - o2.posi;
            }
            if (o1.isUp != o2.isUp) {
                return o1.isUp ? -1 : 1;
            }
            return 0;
        }
    }
    public List<List<Integer>> buildingOutline(int[][] buildings) {
        Node[] nodes = new Node[buildings.length * 2];
        for (int i = 0; i < buildings.length; i++) {
            nodes[i * 2] = new Node(buildings[i][0], buildings[i][2], true);
            nodes[i * 2 + 1] = new Node(buildings[i][1], buildings[i][2], false);
        }
        Arrays.sort(nodes, new MyComparator());
        TreeMap<Integer,Integer> htMap = new TreeMap<>();
        TreeMap<Integer,Integer> pmMap = new TreeMap<>();
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i].isUp) {
                if (!htMap.containsKey(nodes[i].h)) {
                     htMap.put(nodes[i].h, 1);
                }else{
                    htMap.put(nodes[i].h, htMap.get(nodes[i].h) + 1);
                }
            }else{
                if (htMap.containsKey(nodes[i].h)) {
                    if (htMap.get(nodes[i].h) == 1) {
                        htMap.remove(nodes[i].h);
                    }else{
                        htMap.put(nodes[i].h, htMap.get(nodes[i].h) - 1);
                    }
                }
            }
            if (htMap.isEmpty()) {
                pmMap.put(nodes[i].posi, 0);
            }else{
                pmMap.put(nodes[i].posi, htMap.lastKey());
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        int start = 0;
        int height = 0;
        for (Integer pos : pmMap.keySet()) {
            Integer curHeight = pmMap.get(pos);
            if (height != curHeight) {//意味着要产生轮廓线了
                if (height != 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(start);
                    list.add(pos);
                    list.add(height);
                    res.add(list);
                }
                start = pos;
                height = curHeight;
            }
        }
        return res;
    }
}
